#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 033. 搜索旋转排序数组.py
@time: 2022/1/10 15:01
@desc: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
> 整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

@解题思路:
    1. 二分查找
    2. 每次二分的mid若不是目标值：
        a. 哪一半是有序的（有序的最左边小于最右边）
        b. 到有序的那一边检查目标是否在这个值域内：
            - 若在，就在该区间内二分查找
            - 不在就在另一个区间二分查找
    3. Ot(logN), Os(1)
'''
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        n = len(nums)
        left, right = 0, n-1
        while left<=right:
            mid = (left+right)//2
            if nums[mid]==target: return mid
            # 检查哪一半是有序的
            if nums[0]<=nums[mid]:
                # 若左半区间有序
                # 检查目标值是否在左半区间中
                if nums[0]<=target<nums[mid]:
                    right = mid - 1
                else:
                    # 如果不在这个区间，就改从右半区间
                    left = mid + 1
            else:
                # 若左半区间无序，则右半区间必有序
                # 检查目标是否在右半区间中
                if nums[mid]<target<=nums[n-1]:
                    left = mid + 1
                else:
                    # 如果不在右半区间，就改从左半区间找
                    right = mid - 1
        return -1

